1. Field of the Invention
The invention relates to a competition arbitration system for, when a plurality of requests (use requests) compete, selecting one of the requests at a high speed and, more particularly, to a new competition arbitration system which can be applied to arbitration or the like of buses of a microprocessor.
2. Related Background Art
For example, since a resources in a computer is finite in general, when a plurality of requests compete, there is a case where the user wants to select one of a number of requests in which use of the resource is intended. There are various arbitration systems for arbitrating them. In this case, with respect to selection of a proper arbitration system, trade-offs of a circuit amount, high speed performance, a band width, costs, an electric power consumption, and the like have to be considered.
FIG. 8 is a constructional diagram showing an example of the conventional daisy-chain competition arbitration systems.
The competition arbitration system has a plurality of (N) devices 10-1 to 10-N such as memories or the like as devices to be arbitrated. Bus interfaces 11-1 to 11-N are provided for the devices 10-1 to 10-N, respectively. The bus interfaces 11-1 to 11-N are connected to a bus 15 for transmitting bus data BD. A bus request signal RQ and a bus release signal RL are outputted from each of the devices 10-1 to 10-N and inputted to a bus arbiter 16.
The bus arbiter 16 has a function for managing the bus request signals RQ and bus release signals RL and sending a bus grant signal GR1 to the device 10-1 and is constructed by, for example, a personal computer (hereinafter, abbreviated to “PC”) of a host and the like. When the bus grant signal GR1 outputted from the bus arbiter 16 is sent to, for example, the device 10-1, bus grant signals GR2 to GRN are subsequently sequentially transferred in the direction from the device 10-1 to the device 10-N.
In such a competition arbitration system, the devices 10-1 to 10-N compete for a use right of the one bus 15, only one certain device (for example, 10-2) can use the bus 15 via the bus interface 11-2 for a predetermined period of time, and other devices (for example, 10-1, 10-3 to 10-N) are made to wait for the use of the bus. This is because it is necessary to prevent a collision of the bus data BD on the bus 15.
The use right of the bus 15 is shifted by propagation of the bus grant signals GR1 to GRN. With respect to such a situation, it can be presumed that the devices 10-1 to 10-N hold a token and the token is transmitted and received among the devices 10-1 to 10-N. That is, the devices 10-1 to 10-N which request the use grant of the bus 15 preliminarily generate the bus request signal RQ. When one of the devices 10-1 to 10-N obtains the token, it can use the bus 15. For the duration time of yielding the bus 15, even if other devices generate the bus request signals RQ, they are made to wait for the use of the bus 15 until a bus release signal RL is issued.
FIG. 9 is a timing chart showing an example of the operation which is executed when the device 10-2 requests the use of the bus 15 in the daisy-chain competition arbitration system of FIG. 8.
For example, with respect to a bus request signal RQ2 from the device 10-2 which was generated before timing t1, since the device 10-2 receives the token when the bus grant signal GR2 is set to the high level at timing t2, the device 10-2 can assure the use right of the bus 15. Thus, data DA2 can be inputted/outputted to/from the bus 15. In this instance, other devices including the device 10-1 which do not issue the bus request signal RQ cannot use the bus 15 simultaneously with it.
In the daisy-chain arbitration system, the transmission and reception of the token are performed by the propagation of the bus grant signals GR1 to GRN, and the devices 10-1 to 10-N sequentially transfer the token in the direction from the device 10-1 to the device 10-N.
According to the daisy-chain arbitration system, since each of the devices 10-1 to 10-N has one chance of getting the bus grant per period of the propagation of the token, although such a system has the bus arbiter 16, it can be regarded as a distributed arbitration system that is fair to all of the devices 10-1 to 10-N. Since such a system is an arbitration system which can be easily understood, it has widely been spread.
FIG. 10 is a constructional diagram of a distributed competition arbitration system showing an example of the conventional distributed arbitration systems.
As a distributed competition arbitration system, for example, the system NuBus used in MAC made by Apple Computer Co. Ltd. in the U.S.A. has been well-known. The distributed competition arbitration system has a plurality of (N) devices 20-1 to 20-N, and bus interfaces 21-1 to 21-N provided for the devices 20-1 to 20-N are connected to a data bus 25 for transmitting the bus data BD. Further, bus masters 22-1 to 22-N provided for the devices 20-1 to 20-N are connected to a request bus 26.
According to the distributed competition arbitration system, a center bus arbiter like a bus arbiter 16 shown in FIG. 8 is not provided. The bus masters 22-1 to 22-N provided for the devices 20-1 to 20-N compare a value of the signal on the bus with their own priorities with reference to the request bus 26 and discriminates whether the bus request signal RQ is withdrawn or not. The last remaining device (one of the devices 20-1 to 20-N) gets the use right of the data bus 25. Such a system is what is called a self-selection system. The request bus 26 is driven by an open-collector and uses a logic such that the “L” level is preferentially set for the purpose of determining the value of the request bus 26.
The distributed competition arbitration system can use a simple construction because the center bus arbiter is unnecessary. However, since a rather special judging system is used, there are not many systems using it.
However, the conventional competition arbitration system has the following problems (A) and (B).    (A) In the daisy-chain competition arbitration system of FIG. 8, since the token is transmitted and received among the devices 10-1 to 10-N, there is a problem such that a propagation delay is large and the larger the number N of devices 10-1 to 10-N is, the longer the arbitration is delayed. Particularly, since all of the devices 10-1 to 10-N depend on the device whose judging speed is the lowest, the band width is limited, and there is a fear such that a request from the device which needs the high speed arbitration is not satisfied. Thus, a transfer speed of the bus 15 is sacrificed and there is a fear such that input/output devices or the like in which high speed performance is required cannot be established. Although such a system is fair in terms of a chance for arbitration, there is a possibility that the bus 15 is indefinitely occupied by the device of a low priority. In this situation, a request from the device of a high priority cannot be satisfied.    (B) In the distributed competition arbitration system of FIG. 10, since all of the devices 20-1 to 20-N need to compare their own priorities with the value on the request bus 26, there is a problem such that it takes time for decision. Since there is a possibility that the device of the high priority occupies the data bus 25, there is a case where limiting means for preventing such occupation is necessary.